# -*- coding: utf-8 -*-

"""剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]"""

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Edge():
    def __init__(self, node, lr) -> None:
        """节点之间的边，node表示上级节点，lr表示向下的左或右节点，0代表左节点，1代表右节点"""
        self.node = node
        self.lr = lr

class Codec:
    """采用前序遍历的形式序列化。
    在反序列化的时候，提前准备可以挂载的边，得益于前序遍历先左后右的特征，左节点边可以用一个临时变量维护，右节点边需要用一个栈来维护"""
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return '[]'

        seq = []
        def do(node: TreeNode):
            nonlocal seq
            if node:
                seq.append(node.val)
            else:
                seq.append(None)

            if node:
                do(node.left)
            if node:
                do(node.right)

        do(root)

        return str(seq)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data = data[1:-1]
        if data == '':
            return None

        data = data.split(', ')
        seq = []
        for d in data:
            if d == 'None':
                seq.append(None)
            else:
                seq.append(int(d))

        p = 0
        root = TreeNode(seq[p])
        left = Edge(root, 0)    # 左节点这个边只需要用一个临时变量来维护
        right_stack = []    # 右节点这个边用一个栈来维护
        right_stack.append(Edge(root, 1))

        size = len(seq)
        p = 1
        while p < size:
            # print('..........')
            # print('left', left)
            # print('right_stack', right_stack)
            # print('seq[p]', seq[p])
            if seq[p] is not None:
                node = TreeNode(seq[p])

                if left:
                    edge = left
                else:
                    edge = right_stack.pop()

                if edge.lr == 0:
                    edge.node.left = node
                else:
                    edge.node.right = node

                left = Edge(node, 0)
                right_stack.append(Edge(node, 1))
            else:
                if left:
                    left = None
                else:
                    right_stack.pop()

            p += 1

        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

codec = Codec()
rs = codec.serialize(codec.deserialize(str([-1,0,None,None,1,None,None])))
print(rs)

